package lc;

import java.util.HashMap;

import ch2linkedlist.Chapter;
import ch2linkedlist.ListNode;

public class RemoveDuplicatesFromSortedList2 {
    public ListNode deleteDuplicates(ListNode head) {
    	if (head == null) {
    		return head;
    	}
    	
    	HashMap<Integer, Integer> count = new HashMap<Integer, Integer>();
    	ListNode n = head;
    	while (n != null) {
    		int val = n.val;
			if (!count.containsKey(val)) {
    			count.put(val, 0);
    		}
			count.put(val, count.get(val)+1);
			n = n.next;
    	}
    	
    	ListNode newHead = head;
    	while (newHead != null && count.get(newHead.val) > 1) {
    		newHead = newHead.next;
    	}
    	if (newHead == null) {
    		return null;
    	}
    	
    	n=newHead;
    	while (n.next != null) {
    		if (count.get(n.next.val) > 1) {
    			n.next = n.next.next;
    		}
    		else {
    			n = n.next;
    		}
    	}
    	return newHead;
    }

    public static void main(String ...strings) {
    	RemoveDuplicatesFromSortedList2 sol = new RemoveDuplicatesFromSortedList2();
    	ListNode head = Chapter.createSampleList(new int [] {1, 1, 2, 3, 3});
    	Chapter.print(head);
    	ListNode deleteDuplicates = sol.deleteDuplicates(head);
    	Chapter.print(deleteDuplicates);
    	
    	head = Chapter.createSampleList(new int [] {1, 1, 2, 2});
    	Chapter.print(head);
    	deleteDuplicates = sol.deleteDuplicates(head);
    	Chapter.print(deleteDuplicates);
    }
}
